1. Field of the Invention
The present invention relates to a method for storing data using a digital file system, and more particularly to an efficient method for storing video data upon an array of multiple storage devices.
2. Description of the Prior Art
It is well known that digital video recorders store video data files or streams upon various types of storage devices for future selectable viewing. This video data is made up of numerous individual digital pictures, sometimes referred to as frames. These frames are still pictures, and must be sequentially run at a high speed to create the effect of motion within the video. The file size of each frame varies, depending upon its quality, dimensions, and other characteristics. The combination of these frames into a single video data file or stream results in the video data having a high volume of information. This file size increases with the duration, quality, dimensions, and other characteristics of the video. As a result, video data is generally larger in size than its traditional data file counterparts, even after various compression routines are performed upon it.
Therefore, the methods and requirements for storing and serving video data differ significantly from those of traditional data files. Video data storage devices must have correspondingly larger storage capacities than their traditional data file counterparts. Video data integrity is another concern, since the loss of a single video segment will result in an incomplete, or even nonfunctional, video. This vulnerability is heightened by the sheer size of the video data; since it occupies a greater proportion of the storage device, it is more likely to be affected by any data corruption or physical damage. This also creates a need for a redundant storage system, where a backup of the video data is securely stored for later use in the event that the original file is somehow corrupted or damaged. This backup video data will have approximately the same file size as that of the original file, thus requiring an additional storage device having similar storage capacities. Finally, expanding the free storage capacity (often by purchasing an additional, larger storage device) is a time-consuming process. It often requires copying the entire video data, or a portion of it, to the new storage device. Unlike copying the smaller traditional data files, copying video data may require a significantly longer amount of time, depending upon its size, the transfer speeds between the storage devices, and various other considerations.
The traditional method for storing and serving video data, and one still commonly used with most personal computers today, is to simply store the entire video data, or large segments of it, upon a single storage device. However, there are four significant problems with such a method. First, the storage device must have adequate free storage capacity. Although the capacities of various storage devices have increased over the years, the demand for lengthier, higher quality video has also increased, making this solution infeasible for storing numerous video data concurrently and on a long term basis. Second, using a single storage device is problematic in that failure of the device may potentially destroy all of the video data stored upon it. Even losing a few sectors of the device may result in substantial damage to the video data, depending upon the specific locations of the video data and the damage. Third, data redundancy is often non-existent, or accomplished simply by copying the video data to a separate, similar storage device. This second device is then removed to a safe location, and generally left unused so as to minimize any risk of damage to it. Fourth, if additional storage capacity is required, the video data generally must be copied in its entirety; the only alternatives are to divide the video data into several segments and place the individual segments onto separate storage devices, or compress the video data further. All three of these alternatives require significant amounts of time, with the last alternative also reducing the video quality.
A variety of inventions have been developed to store and serve video data, many of which store the video data upon multiple storage devices. Most of these inventions also provide other features, although those features will not be addressed in the present discussion because they are unrelated to the scope of this invention. For example, U.S. Pat. Nos. 5,574,662 and 6,289,172 disclose storage methods for storing video data upon an array of multiple storage devices. The inventions divide the single video data file or stream into various individual segments, where the size of the segments are based upon the particular video format and hardware characteristics, such as seek times, bandwidth, and I/O data rates. Each segment consists of numerous frames, the exact number depending upon the size of the video segment relative to the overall video data. The inventions then sequentially place the segments upon the different storage devices within the array.
U.S. Pat. No. 5,732,239 discloses a storage method that also divides video data into various segments for storage upon multiple storage devices. The video data is divided into a number of segments proportionate to the number of storage devices within the array. The invention then places the segments upon the different storage devices, either in or out of sequential order. If new storage devices are added to widen the array, the invention reorganizes the segments, either by moving all of the segments, or only those necessary to create a balanced distribution across the entire array.
U.S. Pat. No. 4,688,106 discloses a storage method that divides video data into its individual frames. These frames are then distributed in a parallel fashion upon the various storage devices within the array. However, in writing the frames to the various storage devices, the invention does not take into consideration the different file sizes of the individual frames; instead, the frames are merely written sequentially to the array.
U.S. Pat. No. 6,360,058 discloses a storage method that divides video data into its individual pixels. These pixels are then distributed throughout the array of storage devices in such a manner that no two neighboring pixels are recorded upon the same storage device. This permits the invention to compensate for damaged or lost pixel information by extrapolating such information from the neighboring pixels.
U.S. Pat. Nos. 5,574,662 and 6,289,172 also disclose a method for file redundancy, particularly by making a concurrent, second recording of the video file data upon a separate storage device. This separate storage device is accessed when the invention is unable to read information from one of its primary devices, or where one primary device is reacting slowly to the data requests. U.S. Pat. No. 6,434,323 discloses a second, but similar, method for file redundancy, where the backup data file is stored upon a tape medium. This redundancy method requires the invention to make backups at regular intervals, and upon certain defined events.
Unfortunately, none of the above described devices are particularly suited to the four goals of preserving the video data stream continuity, optimizing the capacity of the storage devices within the array, minimizing or negating the need for any redundant storage, and at the same time, providing a means for easily expanding the overall storage capacity of the array. Most of the above described inventions divide video data into various segments. Each of these segments contains multiple consecutive frames. The loss of any one segment, whether by data corruption or physical damage to a storage device, will cause the video to freeze at, or skip over, the affected location. Depending upon the size of the video segment relative to the overall video data, this malfunction may last anywhere from a few seconds to several minutes. Any video data stored within this affected time interval is unviewable.
Other inventions do not adequately optimize the capacities of the various storage devices, or fail to account for their limitations. For example, the invention of the '106 patent records the individual frames sequentially upon an array of multiple storage devices. It does not consider the fact that the individual frames may be of varying sizes. Thus, the sequential placement of individual frames upon the array will result in several storage devices containing wide discrepancies in free storage capacity; in other words, one storage device will have more information stored upon it than another, even though both devices will contains the same number of frames. This results in a load-balancing problem, in which one device is used more heavily than another, such that the entire video data stream may be delayed while waiting for the overburdened storage device to process a frame request. The invention '058 patent exacerbates this problem by requiring each storage device to process the video data request on a pixel by pixel basis; this process will require more work of each storage device, and may hinder video playback even further due to hardware limitations of the particular storage device.
Furthermore, only the invention of the '239 patent expressly provides a method for redistributing video data upon the addition of new storage devices to an existing array. The '239 invention, in one of its embodiments, takes into consideration the free storage capacity of each storage device. However, since the '239 invention divides its video data into various segments of equal size, this redistribution method consists simply of ensuring that each storage device contains an equal number of video segments, either by redistributing all of the video data segments sequentially upon the widened array, or by shifting only the excess segments onto the new storage devices.
It is therefore desirable to provide a single method for storing video data upon an array of multiple storage devices in such a manner as to preserve video data stream continuity, optimize the capacity of the storage devices within the array, minimize or negate the need for any redundant storage, and at the same time, provide a means for easily expanding the overall storage capacity of the array.